package com.gitee.huxing.algorithmic.daily;

import java.util.Arrays;
import java.util.Map;

/**
 * @Description: 火柴拼正方形
 * 你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i个火柴棒的长度。
 * 你要用 所有的火柴棍拼成一个正方形。你 不能折断 任何一根火柴棒，
 * 但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。
 *
 * 如果你能使这个正方形，则返回 true ，否则返回 false

 * @ProjectName: algorithmic-pactice
 * @Package: Makesquare
 * @ClassName: Makesquare
 * @Author: huxingmale
 * @DateTime: 2022-06-01 9:08
 */
public class MakeSquare {

    public static void main(String[] args) {
        MakeSquare square = new MakeSquare();
        int[] matchsticks = new int[]{1, 1, 2, 2, 2};
        System.out.println(square.makeSquare(matchsticks));
    }

    public boolean makeSquare(int[] matchsticks) {
        // 统计数组的从长度 至少为4的倍数才有机会组成正方形
        int totalLen = Arrays.stream(matchsticks).sum();
        if (totalLen % 4 != 0){
            return false;
        }
        // 数组排序
        Arrays.sort(matchsticks);
        for (int i = 0, j = matchsticks.length - 1; i < j; i++, j--){
            int temp = matchsticks[i];
            matchsticks[i] = matchsticks[j];
            matchsticks[j] = temp;
        }
        int[] edges = new int[4];
        return dfs(0, matchsticks, edges, totalLen / 4);
    }

    public boolean dfs(int index, int[] matchsticks, int[] edges, int len){
        if (index == matchsticks.length){
            return true;
        }
        for (int i = 0; i < edges.length; i++){
            edges[i] += matchsticks[index];
            if (edges[i] <= len && dfs(index + 1, matchsticks, edges, len)){
                return true;
            }
            edges[i] -= matchsticks[index];
        }
        return false;
    }
}
